#!/usr/bin/env python
# -*-coding:utf-8 -*-

__all__ = ['CompositeTaskQueue', 'append', 'removeAt', 'sorted', 'size', '__iter__', '__getitem__']

from linked_list import LinkedList, LinkedListIter
from composite_task import CompositeTask

class CompositeTaskQueue(object):
    """
    带优先级的任务队列。
    """
    
    def __init__(self):
        """
        创建一个复合任务队列。
        """
        self._ctasks = LinkedList()
        self._index = 0

    def sort(self, i):
        """
        重新排列链表self._ctasks中的第i个节点。
        """
        ctask = self._ctasks.get(i)
        j = self.insertIndex(ctask, skip=i)
        self._ctasks.move(i, j)
        return j
        
    def _partition(self, begin, end):
        pivot = begin
        for i in range(begin+1, end+1):
            #print('comparing {0} (index {1}) and {2} (index {3})'.format(self._ctasks[i].getNextUncompletedTask().getPriority(), i, 
            #                                                             self._ctasks[begin].getNextUncompletedTask().getPriority(), begin))
            if self._ctasks[i] > self._ctasks[begin]:
                pivot += 1
                self._ctasks.swap(i, pivot)
                #print('A swapping {0} and {1}'.format(i, pivot))
        self._ctasks.swap(begin, pivot)
        #print('B swapping {0} and {1}'.format(pivot, begin))
        return pivot
        
    def _quicksort(self, begin, end):
        if begin >= end:
            return
        pivot = self._partition(begin, end)
        self._quicksort(begin, pivot-1)
        self._quicksort(pivot+1, end)

    def quicksort(self, begin=0, end=None):
        if end is None:
            end = self._ctasks.size() - 1
        return self._quicksort(begin, end)
    
    def move(self, fr, to):
        self._ctasks.move(fr, to)
    
    def insertIndex(self, ctask, skip=None):
        lo = 0
        if skip is not None:
            hi = self._ctasks.size() - 1
        else:
            hi = self._ctasks.size()
            
        while lo < hi:
            mid = (lo+hi)//2
            if skip is not None and mid >= skip:
                mid_ctask = self._ctasks.get(mid + 1)
            else:
                mid_ctask = self._ctasks.get(mid)
            if mid_ctask <= ctask: 
                hi = mid
            else:
                lo = mid + 1
        if skip is not None:
            if lo > skip:
                lo -= 1
        return lo
                        
    def append(self, ctask, sort=True):
        """
        在任务队列中添加一个复合任务。该任务将会由Dispatcher分配给机器人，然后其中的简单任务将一一由Scheduler调度。
        :param ctask: 添加到队列的任务（CompositeTask对象）。
        """
        if isinstance(ctask, CompositeTask):
            if sort:
                i = self.insertIndex(ctask)
                #print('insert', ctask, 'at', i)
                self._ctasks.insert(i, ctask)
            else:
                self._ctasks.add(ctask)
                #print('add', ctask)
        else:
            raise ValueError("Argument ctask must be an instance of class CompositeTask.")

    def removeAt(self, idx):
        """
        从任务队列中删除一个任务。
        :param idx: 需要删除的复合任务（CompositeTask对象）的下标。
        """
        self._ctasks.remove(idx)
        
    def clear(self):
        s = self.size()
        for _ in range(s):
            self.removeAt(0)

    def size(self):
        """
        复合任务队列中包含的复合任务数量。
        :return: 任务队列中包含的复合任务数量。
        """
        return self._ctasks.size()
        
    def isEmpty(self):
        return self._ctasks.empty()
        
    def __getitem__(self, idx):
        """
        获取复合任务队列的下标为idx的复合任务。
        :return: 复合任务队列的一个迭代器。
        """
        return self._ctasks.get(idx)
        
    def __iter__(self):
        return LinkedListIter(self._ctasks)
        
    
def testCompositeTaskQueue():
    from task import Task
    
    ctask_queue = CompositeTaskQueue()
    
    ctask = CompositeTask(0)
    ctask.add(Task(10, '1', '1', priority=0.7))
    ctask_queue.append(ctask)
    
    ctask = CompositeTask(0)
    ctask.add(Task(10, '2', '2', priority=0.8))
    ctask_queue.append(ctask)
    
    ctask = CompositeTask(0)
    ctask.add(Task(10, '3', '3', priority=0.2))
    ctask_queue.append(ctask)
    
    ctask = CompositeTask(0.1)
    ctask.add(Task(10, '4', '4', priority=0.1))
    ctask_queue.append(ctask)
    
    ctask = CompositeTask(0.1)
    ctask.add(Task(10, '4', '4', priority=0.5))
    ctask_queue.append(ctask)
    
    print('Before sorting ...')
    for i in range(4):
        print(ctask_queue[i].getNextUncompletedTask().getPriority())
        
    ctask_queue.quicksort()
    
    print('After sorting ...')
    for i in range(4):
        print(ctask_queue[i].getNextUncompletedTask().getPriority())
        
if __name__ == '__main__':
    testCompositeTaskQueue()